package com.heng.test.bloomFilter;

import java.util.BitSet;
import java.util.Random;

public class BloomFilter<T> {
    // 一个位数组，用于存储数据
    private final BitSet bitSet;
    // 位数组的大小
    private final int bitSetSize;
    // 使用的哈希函数数量
    private final int numHashFunctions;
    private final Random random;

    // 布隆过滤器构造函数
    public BloomFilter(int capacity, int numHashFunctions) {
        this.bitSetSize = capacity;
        this.numHashFunctions = numHashFunctions;
        this.bitSet = new BitSet(bitSetSize);
        this.random = new Random();
    }

    /** 添加元素到布隆过滤器
     * - 将元素通过多个哈希函数进行散列。
     * - 将这些哈希值映射到位数组中对应的索引位置，并将这些位置的值设为1。
     * @param value
     */
    public void add(T value) {
        for (int i = 0; i < numHashFunctions; i++) {
            int hash = hash(value, i);
            bitSet.set(Math.abs(hash % bitSetSize), true);
        }
    }

    /** 检查元素是否存在
     * - 将元素通过同样的哈希函数散列。
     * - 检查这些散列值对应的位数组位置是否都为1，
     * 如果是，则说明元素可能存在（但不保证）；如果有任意位置为0，则说明元素一定不存在。
     * @param value
     * @return
     */
    public boolean mightContain(T value) {
        for (int i = 0; i < numHashFunctions; i++) {
            int hash = hash(value, i);
            if (!bitSet.get(Math.abs(hash % bitSetSize))) {
                return false;
            }
        }
        return true;
    }

    // 哈希函数，用于生成多个不同的哈希值
    private int hash(T value, int seed) {
        random.setSeed(value.hashCode() + seed);
        return random.nextInt();
    }

    // 测试布隆过滤器
    public static void main(String[] args) {
        int capacity = 100; // 位数组大小
        int numHashFunctions = 5; // 使用的哈希函数数量

        BloomFilter<String> bloomFilter = new BloomFilter<>(capacity, numHashFunctions);

        // 添加元素
        bloomFilter.add("apple");


        // 检查元素是否存在
        System.out.println(bloomFilter.mightContain("apple"));  // 可能存在
        System.out.println(bloomFilter.mightContain("banana")); // 可能存在
        System.out.println(bloomFilter.mightContain("grape"));  // 一定不存在

        System.out.println(bloomFilter.bitSet);
    }
}
